13
Esbozo de implementación ( ¿Procesos bloqueados? )
espLapso => Muy parecido a preparados, sólo que es necesario indicar cuándo despertarles o cuánto falta para despertarles, …
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 97
(Gp:) 98
(Gp:) 99
(Gp:) 100
(Gp:) 50
(Gp:) type descriptorProceso is
record
pid: NATURAL;
estado: unEstado;
sig: idProceso;
lapso: NATURAL;
end record;
espLapso : unaCola;
(Gp:) 10
(Gp:) 5
(Gp:) 25
El campo sig me sigue sirviendo para encadenar
Otras formas de implementarlo:
(Gp:) 5
(Gp:) 5
(Gp:) 15
(Gp:) 4
(Gp:) 50
(Gp:) 97
14
Esbozo de implementación ( ¿Procesos bloqueados? )
espFinHijo => El fin de un hijo sólo puede estar esperándolo su Padre. Puede no ser necesaria una cola.
type descriptorProceso is
record
pid: NATURAL;
padre: idProceso;
estado: unEstado;
sig: idProceso;
lapso: NATURAL;
end record;
El Padre (P) hace wait (H):
— Localizar H en procesos => h
if h.estado = zombie then
Liberar recursos del Hijo y
continuar al Padre
else — hijo vivo
p.estado:=espFinHijo; p.sig:=h;
liberar CPU;
Un Hijo(H) termina exit:
If (p.estado = espFinHijo) & (p.sig = h) then
liberar recursos Hijo y continuar Padre
else
h.estado := zombie y liberar CPU
15
Esbozo de implementación ( Concluyendo )
maxProcesos : constant := 100;
type idProceso is NATURAL range 0..maxProcesos;
type unEstado is (ejecutandose, preparado,
espLapso, espFinHijo, zombie);
type descriptorProceso is
record
pid: NATURAL;
padre: idProceso;
estado: unEstado;
sig: idProceso;
lapso: NATURAL;
SP: address;
memoria: ———-;
ficheros: ———-;
tiempos: ———-;
end record;
type unaCola is
record
primero: idProceso := 0;
ultimo: idProceso := 0;
end record;
procesos : array [1..maxProcesos] of
descriptorProceso;
ejecutandose: idProceso;
preparados, espLapso: unaCola;
¿ fork y exec ?
16
Campos en una entrada a la tabla de procesos
Esbozo de implementación ( Otro ejemplo )
17
Esbozo de implementación ( El Cambio de Contexto )
Causas?
(Gp:) Llamada al Sistema
Fin de Proceso
Bien/Mal
Interrupción
(Gp:) Trap
(Gp:) (E/S, F.R.)
(Gp:) Mecanismo similar
Supongamos como causa "Fin de Rodaja"
(Gp:) ejecu-
tándose
(Gp:) Pi
(Gp:) Hw
(Gp:) (1)
(1) Reconocimiento de la interrupción
(Gp:) S.O.
(Gp:) Pj
(Gp:) Ens.
(Gp:) (2)
(2) Salvar reg (Pi) y conmutar de pila
(Gp:) C/Modula/Ada
(Gp:) (3)
(3) 1 Recorrer dormitorio
2 Elegir siguiente proceso
(Gp:) Ens.
(Gp:) (4)
(4) Recuperar reg (Pj) y cederle control
(Gp:) Planificador
(Gp:) Dispatcher
¿No hay procesos preparados?
18
(Gp:) Vector de Interrupciones
(Gp:) S.O.
Esbozo de implementación ( El Cambio de Contexto )
———-
———-
sleep(10)
———-
———-
exit(0)
——-
——-
——-
——-
——-
——-
——-
——-
——-
——-
——-
——-
(Gp:) TRAP #0
——-
——-
——-
——-
——-
(Gp:) INT 3
———-
divu d5,d0
———-
——-
——-
——-
——-
——-
(Gp:) DIV 0
(Gp:) Se salva el SR y PC
(Gp:) ——-
——-
——-
——-
——-
——-
——-
——-
(Gp:) Cambio de contexto
19
Threads ( Visión abstracta )
Modelo de procesos más común ? Espacios de direcciones disjuntos
(Gp:) Registros
Código
Datos, Pila
Ficheros
(Gp:) Pi
(Gp:) Registros
Código
Datos, Pila
Ficheros
(Gp:) Pj
(Gp:) fork
(Gp:) exec
(Gp:) ls.exe
Facilita protección Pi?Pj, pero:
Creación laboriosa
Cambio de contexto pesado
(procesador + entorno) TLB's, cachés, …
Comunicación vía mensajes
más seguro pero más lento
¿Y si los procesos son cooperantes?
Objetivo común
Colaboración vs agresión
Protección más laxa
Pueden desear mantener datos comunes con los menores costes de tiempo
20
(Gp:) BD utilidades
Threads ( Visión abstracta )
Procesos Ligeros ? Espacios de direcciones no disjuntos
(Gp:) Registros
Pila
(Gp:) Registros
Pila
(Gp:) Código, Datos
Ficheros
(Gp:) Ti
(Gp:) Tj
Servidor de localización de utilidades
(Gp:) C1
(Gp:) C2
(Gp:) Cn
(Gp:) S
(Gp:) consulta
(Gp:) alta
(Gp:) consulta
(Gp:) petición
respuesta
(Gp:) petición
(Gp:) petición
¡ Muy eficaz con multiprocesadores !
Soportados de dos formas:
En el espacio del S.O.
En el espacio del Usuario
Biblioteca
21
Threads ( "Linux" )
int __clone (int (*fn) (void *arg), void *child_stack, int flags, void *arg)
(Gp:) Como fork sólo que crea un Thread "Específico de Linux"
Thread soportado como tal por el S.O. (no portable)
(Gp:) Biblioteca pthread (API POSIX 1003.1c)
int pthread_create (pthread_t * thread, atributos, funcion, argumentos)
pthread_t pthread_self (void)
int pthread_exit (void *estado)
int pthread_join (pthread_t thread, void **estado)
……………………………………………
……………………………………………
¿ fork + threads ?
22
Threads ( Ejemplos de uso: tonto.c )
#include < pthread.h>
#include < stdio.h>
int main (int argc, char *argv[]){
pthread_t tA, tB;
int datoA=0; datoB=0;
pthread_create(&tA, NULL, A, NULL);
pthread_create(&tB, NULL, B, NULL);
pthread_join (tA, NULL);
pthread_join (tB, NULL);
exit (0);
}
void *B (void *basura) {
datoB = 2000;
sleep (5);
printf ("datoA=%dn", datoA);
pthread_exit (NULL);
}
void *A (void *basura) {
datoA = 1000;
sleep (5);
printf ("datoB=%dn", datoB);
pthread_exit (NULL);
}
(Gp:) datoC=0;
(Gp:) int datoC;
(Gp:) int datoC;
(Gp:) ?
Threads ( Ejemplos de uso: cuentaPar.c )
cuentaPar.c: Número de apariciones de un número en un vector
(Gp:) 6 2 0 7 4 9 3 4 9 8 0 6 7 9 6 0 6 7 9 8 6 2 5 2 6 4 7 9 3 5 2 1 7 3 2 6 6 4 4 0
(Gp:) const
N = 40;
objetivo = 6;
numCPUs = 4;
var
vector array[1..N] of integer;
¿ Algoritmo paralelo ?
(Gp:) T0
(Gp:) T1
(Gp:) T2
(Gp:) T3
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
(Gp:) +
(Gp:) 8
23
(Gp:)
int longRodaja, numVecesLocal[MAX_ESCLAVOS], *vector;
void *esclavo (void *parametro) { ….. }
int main (int argc, char *argv[]) {
int i, numVeces, cardinalidad = atoi (argv[1]);
int numEsclavos = atoi (argv[2]);
pthread_t pids[MAX_ESCLAVOS];
// Pedir memoria e inicializar vector
// Crear esclavos y esperar a que terminen su trabajo
for (i = 0; i < numEsclavos; i++)
pthread_create (&pids[i], NULL, esclavo, (void *) i);
for (i = 0; i < numEsclavos; i++)
pthread_join (pids[i], NULL);
// Sumar los valores de todos e informar del resultado
numVeces = numVecesLocal[0];
for (i = 1; i < numEsclavos; i++)
numVeces = numVeces + numVecesLocal[i];
printf ("Veces que aparece = %dn", numVeces);
}
(Gp:) %cuentaPar 1000000 4
Threads ( Ejemplos de uso: cuentaPar.c )
24
// Variables globales
int longRodaja, numVecesLocal[MAX_ESCLAVOS], *vector;
void *esclavo (void *parametro) {
int yo, inicio, fin, i, j, numVeces;
yo = (int) parametro;
inicio = yo * longRodaja;
fin = inicio + longRodaja;
// Buscar en mi parte del vector
numVeces = 0;
for (i = inicio, i < fin; i++)
if (vector[i] == NUM_BUSCADO) numVeces++;
numVecesLocal[yo] = numVeces;
pthread_exit (NULL);
}
25
Threads ( Ejemplos de uso: cuentaPar.c )
(Gp:) 5
(Gp:) 1,286
(Gp:) 4,26
(Gp:) 0,85
(Gp:) 6
(Gp:) 1,127
(Gp:) 4,86
(Gp:) 0,81
(Gp:) 7
(Gp:) 1,113
(Gp:) 4,92
(Gp:) 0,70
(Gp:) 8
(Gp:) 0,998
(Gp:) 5,49
(Gp:) 0,69
(Gp:) cuentaPar 400.000.000 1..8 // Recorriéndolo diez veces
(Gp:) 2 Xeon E5520 Quad
2,26GHz . 8ML3 . 12GB . 500GB
Threads ( Ejemplos de uso: cuentaPar.c )
26
(Gp:) Esclavos
(Gp:) Tiempo
(Gp:) Aceleración
(Gp:) Eficiencia
(Gp:) 1
(Gp:) 5,480
(Gp:) 2
(Gp:) 2,721
(Gp:) 2,01
(Gp:) 1,01
(Gp:) 4
(Gp:) 1,408
(Gp:) 3,89
(Gp:) 0,97
(Gp:) An = T1 / Tn
(Gp:) En = An / n
sortPar.c: Ordenar un vector en memoria
(Gp:) 3 8 15 2 4 1 7 10 6 14 13 5 11 9 12 16
(Gp:) T0
(Gp:) T1
(Gp:) T2
(Gp:) T3
(Gp:) 2 3 8 15 1 4 7 10 5 6 13 14 9 11 12 16
(Gp:) ordenar
(Gp:) 1 2 3 4 7 8 10 15 5 6 9 11 12 13 14 16
(Gp:) T0
(Gp:) T2
(Gp:) mezclar
(Gp:) T0
(Gp:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
(Gp:) mezclar
Threads ( Ejemplos de uso: sortPar.c )
27
sortPar.c: Ordenar un vector en memoria [Refinamiento]
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:) D
(Gp:) E
(Gp:) F
(Gp:) G
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 0
(Gp:) 2
(Gp:) 0
esclavo (yo: integer);
ordenarRodaja(yo);
case yo of
0: mezclar(A,B,E); mezclar(E,F,G);
1: ;
2: mezclar(C,D,F);
3: ;
end;
?
(Gp:) La mezcla es destructiva => vector auxiliar
(Gp:) Va
(Gp:) Va
(Gp:) Vb
(Gp:) Va
Mezclar requiere haber ordenado . => semáforos
Threads ( Ejemplos de uso: sortPar.c )
28
sem_init
sem_wait
sem_post
#define MAX_ENTERO 10000
#define MAX_ESCLAVOS 4 // Solo funciona con 4 esclavos
//————– VARIABLES GLOBALES ——————————-
int cardinalidad, longRodaja;
int *vector, *vectorBis;
sem_t S1a0, S3a2, S2a0;
void imprimir (int *vector) {
int i;
printf ("Contenido del vectorn");
printf ("====================n");
for (i=0; i< cardinalidad; i++) {
printf ("%6d ", vector[i]);
if ((i%10) == 0) printf ("n");
}
printf ("n");
}
void mezclar (int i, int longRodaja, int *vOrg, int *vDst) {
int iDst, iTope, j, jTope;
iTope = i + longRodaja;
j = iTope;
jTope = j + longRodaja;
for (iDst = i; iDst < jTope; iDst++) {
if (i == iTope ) vDst[iDst] = vOrg[j++];
else if (j == jTope ) vDst[iDst] = vOrg[i++];
else if (vOrg[i] < vOrg[j]) vDst[iDst] = vOrg[i++];
else vDst[iDst] = vOrg[j++];
}
}
Threads ( Ejemplos de uso: sortPar.c )
29
void *esclavo(void *parametro) {
int yo, inicio, fin, i, j, imenor, menor;
int unCuarto, unMedio;
yo = (int) parametro;
inicio = yo * longRodaja;
fin = inicio + longRodaja;
unMedio = cardinalidad / 2;
unCuarto = cardinalidad / 4;
// Ordenar por insercion directa
for (i = inicio; i < fin; i++) {
imenor = i; menor = vector[i];
for (j = i; j < fin; j++)
if (vector[j] < menor) {
imenor = j; menor = vector[j];
}
vector[imenor] = vector[i];
vector[i] = menor;
}
// Fase de mezclas. Solo valida para 4 esclavos
switch (yo) {
case 0: sem_wait (&S1a0); mezclar(0, unCuarto, vector, vectorBis);
sem_wait (&S2a0); mezclar(0, unMedio, vectorBis, vector);
break;
case 1: sem_post (&S1a0); break;
case 2: sem_wait (&S3a2); mezclar(unMedio, unCuarto, vector, vectorBis);
sem_post (&S2a0); break;
case 3: sem_post (&S3a2); break;
default: printf ("Errorn"); break;
}
pthread_exit(NULL);
}
Threads ( Ejemplos de uso: sortPar.c )
30
int main( int argc, char *argv[] ) {
int i, numEsclavos;
pthread_t pids[MAX_ESCLAVOS];
cardinalidad = atoi(argv[1]);
numEsclavos = MAX_ESCLAVOS;
longRodaja = cardinalidad / numEsclavos;
// Pedir memoria e inicializar el vector
vector = malloc(cardinalidad * sizeof(int));
vectorBis = malloc(cardinalidad * sizeof(int));
for (i=0; i< cardinalidad; i++)
vector[i] = random() % MAX_ENTERO;
imprimir(vector);
// Inicializar semaforos para sincronizar
sem_init (&S1a0, 0, 0);
sem_init (&S3a2, 0, 0);
sem_init (&S2a0, 0, 0);
// Crear esclavos y esperar a que terminen su trabajo
for (i=0; i< numEsclavos; i++)
pthread_create (&pids[i], NULL, esclavo, (void *) i);
for (i=0; i< numEsclavos; i++)
pthread_join (pids[i], NULL);
imprimir(vector);
return (0);
}
sort 200000 => 8:350
sortPar 200000 => 2:100
Threads ( Ejemplos de uso: sortPar.c )
31
32
pthread_create pthread_join
pthread_exit pthread_self
Threads ( En el espacio de usuario )
(Gp:) El S.O. no los soporta
Cambio contexto rápido
Distintos planificadores
(Gp:) read, . ¡ Bloqueantes !
Falta de página
¡Planificación expulsora!
33
Threads ( En el espacio del S.O. )
(Gp:) ?
34
Comunicación entre Procesos
Los procesos cooperantes necesitan mecanismos para sincronizarse y comunicarse información de forma segura
Sincronización ? Ordenación temporal de la ejecución de procesos
A antes que B
(Gp:) Canal de Panamá
Tortilla de patatas
Batir Pelar Pelar
Huevos Cebollas Patatas
Mezclar, Añadir Sal y Freir
Comunicación ? Paso de información entre tareas
Síncrona o Asíncrona
Filtros Unix:
who | wc | sed -e 's/ [ ]*/:/g' | cut -d: -f2
35
Condiciones de Carrera
La falta de sincronismo entre procesos cooperantes da problemas
Canal de Panamá ? Barco encallado
Tortilla de Patatas ? No hay quien se la coma
Uso de datos / recursos comunes ? Inconsistencia
El empresario y los taxistas:
(Gp:) ¡Que buen negocio!
(Gp:) ¡Me tangan!
36
Condiciones de Carrera (Modelización con threads)
Ingreso de Taxista 1 = 80729
Ingreso de Taxista 2 = 80618
Total recaudacion = 161096
(Gp:) +
(Gp:) 161347
(Gp:) int cuenta;
void *taxista(void *parametro) { ….. }
int main( int argc, char *argv[] ) {
int i, numEsclavos;
pthread_t pids[MAX_ESCLAVOS];
numEsclavos = atoi(argv[1]);
cuenta = 0;
// Crear esclavos y esperar a que terminen su trabajo
for (i=0; i< numEsclavos; i++)
pthread_create (&pids[i], NULL, taxista, (void *) i);
for (i=0; i< numEsclavos; i++)
pthread_join (pids[i], NULL);
printf ("Total recaudacion = %dn", cuenta);
return (0);
}
37
(Gp:) Ingreso
Condiciones de Carrera (Modelización con threads)
void *taxista (void *parametro) {
// Variables
recaudacion = 0; mio = 0;
do {
espera = random() % MAX_ESPERA;
for (i=1; i< espera; i++);
importe := random (maxImporte);
mio := mio + (importe / RATIO_TAXISTA);
cuenta := cuenta + importe –
(importe / RATIO_TAXISTA);
recaudacion := recaudacion + importe;
} while (mio < SUELDO_DIA);
printf ("Ingreso de Taxista %d = %dn",
yo, recaudacion – mio);
pthread_exit (NULL);
}
(Gp:) Hacer Carrera
(Gp:) Buscar Cliente
38
Condiciones de Carrera (Modelización con threads)
(Gp:) Threads
(Gp:) pc1:4Cores
(Gp:) pc9:8Cores
(Gp:) 2
(Gp:) 4
(Gp:) 8
(Gp:) 16
(Gp:) 32
(Gp:) Fallos x 1.000
(Gp:) 7
(Gp:) 64
(Gp:) 230
(Gp:) 533
(Gp:) 830
(Gp:) 207
(Gp:) 926
(Gp:) 1.000
(Gp:) 1.000
(Gp:) 1.000
39
3: cuenta := cuenta + importe
Condiciones de Carrera (El problema)
(Gp:) 3.1: PUSH importe
3.2: PUSH cuenta
3.3: ADDP
3.4: POP cuenta
3.1, 3.2
(Gp:) T1
(Gp:) T2
(Gp:) 5.000
(Gp:) cuenta
(Gp:) 10.000
(Gp:) T1.importe
(Gp:) 3.3
(Gp:) 5.000
(Gp:) 10.000
(Gp:) T1.SP
3.1, 3.2
(Gp:) 1.500
(Gp:) T2.importe
(Gp:) 3.3
(Gp:) 5.000
(Gp:) 1.500
(Gp:) T2.SP
3.3, 3.4
(Gp:) 15.000
(Gp:) 15.000
(Gp:) cuenta
3.3, 3.4
(Gp:) 6.500
(Gp:) cuenta
(Gp:) 6.500
¿problema?
40
Exclusión mutua y Región crítica (La solución)
(Gp:) RC
(Gp:) RC
(Gp:) Aquí como
máximo un Pi
(Gp:) Exclusión
Mutua
(Gp:) Integridad Datos Comunes
(Gp:) Aquí cero,
uno o más Pi
Los Pi indicarán cuándo EntranEnRC y cuándo SalenDeRC
41
Exclusión mutua y Región crítica (La solución)
EntrarEnRC;
cuenta := cuenta + importe –
(importe div ratioTaxista);
SalirDeRC;
REQUISITOS
En una misma Región Crítica no más de un proceso
Sin supuestos: #µP, #Pi, velocidades relativas, …..
Ningún Pi fuera de su Región Crítica bloqueará a otros Pj
Decisión de quién entra a una Región Crítica en un tiempo finito
42
Implementación de la Exclusión Mutua
Mecanismos:
Inhibición de interrupciones . Semáforos
Cerrojos (espera activa) . Monitores
(Gp:) Hw
(Gp:) Sw
(Gp:) Lenguaje
(Gp:) S.O.
Inhibición de interrupciones
Taxistas
InhibirInterrupciones
cuenta := cuenta + importe
PermitirInterrupciones
RC muy corta o pueden
perderse interrupciones
Exclusión total vs parcial
DirecciónGeneralDeTráfico
repeat
aguardarAgazapados y ¡foto!
InhibirInterrupciones
numeroMultas++
PermitirInterrupciones
until cubiertoCupo
Sólo válido en monoprocesador
Peligroso en manos del usuario
Útil dentro del propio S.O.
43
Implementación de la Exclusión Mutua ( Cerrojos )
Una variable "cerrojo" por cada RC distinta que indica Libre/Ocupada
(Gp:) Taxistas
Entrar (RCTaxistas)
cuenta := cuenta + importe
Salir (RCTaxistas)
(Gp:) Guardia Civil
Entrar (RCDGT)
numeroMultas++
Salir (RCDGT)
(Gp:) while RCT = ocupada do null;
RCT := ocupada
cuenta := cuenta + importe;
RCT := libre
(Gp:) entrar tst.b RCT
bnz entrar
move.b #$FF,RCT
push importe
push cuenta
addp
pop cuenta
salir move.b #$00,RCT
RCT dc.b 0
¡ No funciona !
44
Implementación de la Exclusión Mutua ( El cerrojo falla )
(Gp:) T1
(Gp:) T2
(Gp:) 00
(Gp:) RCT
—————-
—————-
entrar tst.b RCT
—————-
—————-
tst.b RCT
bnz entrar
move.b #$FF,RCT
—————-
—————-
(Gp:) T1.SR
(Gp:) Z
(Gp:) 1
(Gp:) FF
(Gp:) RCT
(Gp:) T2 dentro RCT
bnz entrar
move.b #$FF,RCT
—————-
—————-
—————-
—————-
(Gp:) FF
(Gp:) RCT
¡¡ T1 también dentro RCT !!
45
Implementación de la Exclusión Mutua ( Un cerrojo seguro? )
(Gp:) El Hw ayuda con una instrucción atómica que consulta y cambia valor
(Gp:) tas.b cerrojo, valor
(Gp:) tst.b cerrojo
move.b valor,cerrojo
Algoritmos: Dekker, Dijkstra, Knuth, Peterson, …….
(Gp:) entrar tas.b RCT,#$FF
bnz entrar
push importe
push cuenta
addp
pop cuenta
salir move.b #$00,RCT
RCT dc.b 0
(Gp:) F.R.
¿Habrá problemas?
(Gp:) No funciona en multiprocesador ya que TAS es ininterrumpible dentro de un procesador, pero supone dos accesos al bus:
1 Lectura del cerrojo
2 Modificación del cerrojo
(Gp:) ¡SI!
46
Implementación de la Exclusión Mutua ( Un cerrojo seguro! )
T1
T2
(Gp:) 00
(Gp:) RCT
—————-
—————-
tas.b RCT,#$FF
—————-
—————-
tas.b RCT,#$FF
bnz entrar
(Gp:) T1.SR
(Gp:) Z
(Gp:) 1
(Gp:) FF
(Gp:) RCT
(Gp:) FF
(Gp:) RCT
bnz entrar
————-
————-
————-
————-
T1 en RCT
(Gp:) FF
(Gp:) RCT
T2 no puede
entrar en RC
mientras está T1
(Gp:) tas.b RCT,#$FF
bnz entrar
47
Implementación de la Exclusión Mutua ( TAS todavía falla! )
TAS ? PedirBus, Leer, PedirBus, Escribir
(Gp:) ?P1 ? T1 PB, L1, PB, E1
(Gp:) ?P2 ? T2 PB, L2, PB, E2
(Gp:) ???
(Gp:) ?P1
(Gp:) ?P2
(Gp:) RCT
(Gp:) L1, E1, L2, E2
T1 T2
(Gp:) L2, E2, L1, E1
T2 T1
(Gp:) L1, L2, E1, E2
T1 T2
tas.b RCT,#$FF
bnz entrar
(Gp:) PH
tasl.b RCT,#$FF
bnz entrar
———————
———————
¡ Todavía dos problemas !
Espera Activa
Inversión de prioridades
(Gp:) PL
(Gp:) deadLock
¿ Qué hacer ?
(Gp:) TASL "TAS with Lock" ? BusLock, Leer, Escribir, BusRelease
(Gp:) ( El Hw nos ayuda )
48
Implementación de la Exclusión Mutua ( RC POSIX )
int pthread_mutex_lock (pthread_mutex_t *regionCritica)
int pthread_mutex_unlock (pthread_mutex_t *regionCritica)
¿Posible implementación (sin espera activa)?
type pthread_mutext_t is
record
libre : BOOLEAN;
cola : unaCola;
end record;
(Gp:) F
(Gp:) RCT
(Gp:) Pi
(Gp:) Pj
lock (RCT):
inhibir interrupciones
salvarEstado(ejecutandose)
if RCT.libre
then RCT.libre = FALSE
else meter (ejecutandose, RCT);
ejecutandose = planificar();
recuperarEstado(ejecutandose)
rte /*Se habilitan interrupciones*/
(Gp:) Multiprocesador
(Gp:) ?
tasl
(Gp:) ¡ Ojo !
49
Implementación de la Exclusión Mutua ( Semáforos )
Soportado por el S.O. garantiza exclusión mutua sin espera activa
type Semaforos is private;
Inicializar (S: Semaforos; Valor: NATURAL);
Bajar (S); — Puede bloquear al proceso (Si Valor = 0)
Subir (S); — Puede desbloquear a UN proceso
(Gp:) Operaciones
Atómicas
Dar soporte a RC con semáforos es fácil:
Inicializar (S_RCT, 1) Inicializar (S_RCGC, 1)
————— —————
Bajar (S_RCT) Bajar (S_RCGC)
Cuenta := Cuenta + Importe numeroMultas++
Subir (S_RCT) Subir (S_RCGC)
————— —————
50
Implementación de la Exclusión Mutua ( Semáforos )
Precisando la semántica:
P.Bajar (S) ? IF Valor(S) > 0 THEN
Valor (P.Bajar(S)) = Valor(S) – 1
ELSE
P deja UCP y se bloquea esperando P'.Subir(S)
P.Subir(S) ? IF Hay_algun_Pi_esperando_en (S) THEN
Sacar a uno de ellos de espera
INDETERMINISMO
Proceso continuado
Proceso que coge UCP
JUSTICIA
ELSE
Valor (P.Subir(S)) = Valor (S) + 1
51
Implementación de la Exclusión Mutua ( Semáforos )
private type Semaforos is record
valor : NATURAL;
cola : unaCola;
end record;
procedure Inicializar (S : out Semaforos;
valor : NATURAL) is
begin
S.valor := valor;
end Inicializar;
Esbozo de implementación:
(Gp:) 0
(Gp:) S
(Gp:) Pi
(Gp:) Pk
(Gp:) Pj
(Gp:) ¿Dónde están los semáforos?
Hacen falta operaciones del estilo: crear, conectarse, destruir
(Gp:) Exclusión mutua, Salvado estado Pi
(Gp:) Dispatcher
52
Implementación de la Exclusión Mutua ( Semáforos )
procedure Bajar (S: in out Semaforos) is begin
if S.valor = 0 then
encolar (ejecutandose, S.cola);
planificar;
else S.valor := S.valor – 1; endif;
end Bajar;
procedure Subir (S: in out Semaforos) is begin
if S.cola.primero /= 0 then
encolar (sacarProceso(S.cola), preparados);
planificar;
else S.valor := S.valor + 1; endif;
end Subir;
53
Implementación de la Exclusión Mutua ( Semáforos POSIX )
int sem_init (sem_t *S, int global, unsigned int valor)
int sem_wait (sem_t *S)
int sem_post (sem_t *S)
int sem_destroy (sem_t *S)
54
Paso de mensajes
Debilidades del Sincronismo + Memoria Común:
Primitivas de bajo nivel (Inhibir Interrupciones, TASL, Semáforos)
Inviable en sistemas débilmente acoplados sin memoria común
(Gp:) Solución: Envío y recepción de mensajes
(Gp:) Porg
(Gp:) Pdst
(Gp:) Enviar (Pdst, msj)
(Gp:) Recibir (Porg, msj)
—–
—–
—–
(Gp:) Escribe
11
—–
—–
—–
—–
—–
—–
11
(Gp:) Lee
Primera aproximación a la sintaxis:
void enviar ( int Pdestino, void recibir ( int Porigen,
char * msj ); char * msj );
¿Puede fallar enviar/recibir?
(Gp:) ?
(Gp:) ?
(Gp:) int
(Gp:) int
Paso de mensajes ( Ejemplos de uso: cuentaParMsj.c )
¿Cómo podría ser cuentaPar.c si no hay memoria común?
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
(Gp:) 6 2 0 .
(Gp:) 0 6 7 .
(Gp:) 6 2 5 .
(Gp:) 2 1 7 .
(Gp:) +
(Gp:) 8
(Gp:) esclavo1
(Gp:) esclavo2
(Gp:) esclavo3
(Gp:) esclavo4
(Gp:) maestro
(Gp:) 6 2 0 .
(Gp:) 0 6 7 .
(Gp:) 6 2 5 .
(Gp:) 2 1 7 .
(Gp:) El vector lo tiene un proceso "maestro"
El maestro: reparte "envía" trabajo a los "esclavos" y
recoge "recibe" resultados
(Gp:) 6 2 0 .
(Gp:) 0 6 7 .
(Gp:) 6 2 5 .
(Gp:) 2 1 7 .
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
55
56
Paso de mensajes ( Ejemplos de uso: cuentaParMsj.c )
(Gp:) #define longRodaja (N/4)
int vector[N], iRodaja;
int veces, vecesLocal;
// Repartir trabajo
iRodaja = 0;
for e in 1..4 {
enviar (e, &vector[iRodaja],
longRodaja);
iRodaja += longRodaja;
}
// Recoger resultados
veces = 0;
for e in 1..4 {
recibir (e, &vecesLocal, 1);
veces += vecesLocal;
}
(Gp:) #define longRodaja (N/4)
int rodaja[longRodaja];
int veces;
recibir (0, rodaja,
longRodaja);
veces = contarEn (rodaja);
enviar (0, &veces, 1);
(Gp:) maestro
(Gp:) esclavo
57
Paso de mensajes (muchas semánticas)
(Gp:) —–
—–
—–
(Gp:) rec (Po, msj)
(Gp:) —–
—–
—–
(Gp:) —–
—–
—–
(Gp:) env (Pd, msj)
(Gp:) —–
—–
—–
(Gp:) Pd
¿Bloqueo?
(Gp:) El bloqueo dependerá de la ? | ? de mensajes
? msj ? Se le entrega a Pd y continua
(Gp:) ? msj ? Se bloquea a Pd hasta
(Gp:) No siempre
(Gp:) Tiempo Real
Tolerancia a Fallos
Bloquear
Bloquear un máximo
No Bloquear
(Gp:) int recibir ( int Porg, char * msj,
int TmaxEsp)
?
7
(Gp:) 0
(Gp:) ?
(Gp:) ?
(Gp:) Po
¿Bloqueo?
(Gp:) ¿Recibió Pd?
(Gp:) Po
Independencia del enlace de comunicación
58
Paso de mensajes (Cuestiones de Diseño)
Mensajes de longitud fija vs variable
Capacidad de almacenamiento 0 .. ?
Envío por copia vs referencia
Comunicación Directa vs Indirecta
(Gp:) Pi B Pj
(Gp:) Pi Pj
(Gp:) Simétrica vs Asimétrica
(Gp:) Unidireccional vs Bidireccional
59
Paso de mensajes (Mensajes de longitud fija vs variable)
Longitud Fija
El S.O. siempre envía el total
(Gp:) La aplicación distingue distintos msj.
Simplifica la gestión de la capacidad de almacenamiento del canal
Longitud Variable
El S.O. envía lo que diga la aplicación
(Gp:) ¿Cómo?
(Gp:) 110
(Gp:) Mensaje de 110 bytes
(Gp:) En el propio mensaje
(Gp:) enviar (Pdest, msj, 110)
(Gp:) En la llamada
60
Paso de mensajes (Mensajes de longitud fija vs variable)
(Gp:) MINIX 3
(Gp:) typedef struct {
int m_source;
int m_type;
union {
mess_1 m_m1;
mess_2 m_m2;
mess_3 m_m3;
mess_4 m_m4;
mess_5 m_m5;
mess_7 m_m7;
mess_8 m_m8;
} m_u;
} message;
(Gp:) m_source
(Gp:) m_type
(Gp:) m1_i1
(Gp:) m1_i2
(Gp:) m1_i3
(Gp:) m1_p1
(Gp:) m1_p2
(Gp:) m1_p3
(Gp:) m_source
(Gp:) m_type
(Gp:) m2_i1
(Gp:) m2_i2
(Gp:) m2_i3
(Gp:) m2_l1
(Gp:) m2_l2
(Gp:) m2_p1
(Gp:) m_source
(Gp:) m_type
(Gp:) m3_i1
(Gp:) m3_i2
(Gp:) m3_p1
(Gp:) m3_ca1
(Gp:) m_source
(Gp:) m_type
(Gp:) m4_i1
(Gp:) m4_i2
(Gp:) m4_i3
(Gp:) m4_i4
(Gp:) m4_i5
Práctica 4: Nueva llamada SO
Proceso70.if (proceso_vivo(84)
(Gp:) 70
(Gp:) 57
(Gp:) 84
(Gp:) # Llamada 57
61
Paso de mensajes (Capacidad de almacenamiento 0..?)
(Gp:) Ilimitada (?)
(Gp:) Po
(Gp:) Pd
(Gp:) Po
(Gp:) Pd
¡Nunca Bloqueo!
(Gp:) Limitada (8)
(Gp:) Po
(Gp:) Pd
(Gp:) Po
(Gp:) Pd
Hueco ? Sin Bloqueo
¡No hay Hueco!
(Gp:) Bloqueo
Sin Bloqueo
Estado = Lleno
(Gp:) Comunicación Asíncrona
(Gp:) Nula (0)
(Gp:) Po
(Gp:) Pd
¡Siempre Bloqueo!
(Gp:) Po
(Gp:) Pd
Espera a Pd.recibir
(Gp:) Po
(Gp:) Pd
(Gp:) Cita "Rendez-vous"
(Gp:) Po
(Gp:) Pd
(Gp:) Comunicación Síncrona
(Gp:) Po sabe que Pd recibió
(Gp:) ¿Y aquí?
62
(Gp:) Po
(Gp:) Pd
Paso de mensajes (Envío por copia vs referencia)
(Gp:) Escribir
—–
—–
—–
(Gp:) env (Pd, msj)
(Gp:) 1
(Gp:) rec (Po, msj)
(Gp:) 2
¡ 2 copias extra por cada envío/recepción !
(Gp:) Leer
—–
—–
—–
(Gp:) Envío por referencia
(Gp:) Po
(Gp:) Pd
(Gp:) pedirBuffer
(Gp:) Escribir
—–
—–
—–
(Gp:) env (Pd, msj)
(Gp:) rec (Po, msj)
Leer
—–
—–
—–
(Gp:) liberarBuffer
Complejidad pedir/liberar Buffer
¿Y si no hay memoria común?
¿Seguridad?
63
Paso de mensajes (Comunicación Directa)
(Gp:) Indicación explícita
(Gp:) A qué proceso se desea enviar
De qué proceso se desea recibir
(Gp:) Cliente
(Gp:) Servidor
(Gp:) ¿15.731 es primo?
(Gp:) SÍ
repeat repeat
read (msjp.num); recibir ( Pc, &msjp);
enviar (Ps, &msjp); enviar ( Pc,
recibir (Ps, &msjr); respuesta(msjp))
imprimir (msjr.esPrimo) forever
forever
(Gp:) Simétrica
(Gp:) Simétrica
64
Paso de mensajes (Comunicación Directa "Características")
(Gp:) Creación automática del enlace Po Pd
Necesidad de conocer los Pid's de los procesos
De Pi a Pj SÓLO un enlace en cada sentido
(Gp:) Cliente
(Gp:) Servidor
(Gp:) esPrimo?
(Gp:) Hora?
(Gp:) Cliente
(Gp:) Servidor
?
(Gp:) 15.731
(Gp:) 0
(Gp:) 1
(Gp:) Tipo de mensaje
¿Todo resuelto?
(Gp:) Cliente
(Gp:) Servidor
P
P
P
P
P
P
P
H
Un enlace asocia SÓLO a dos procesos
65
Paso de mensajes (Un enlace asocia SÓLO a dos procesos)
(Gp:) C1
(Gp:) C2
(Gp:) S
(Gp:) C1
(Gp:) C2
(Gp:) S
(Gp:) repeat
if recibir (PC1, &msjp ) then
enviar (PC1, respuesta (msjp));
elsif recibir (PC2, &msjp ) then
enviar (PC2, respuesta (msjp));
forever
(Gp:) Servidor
Inanición
Espera Activa
(Gp:) , 1
(Gp:) , 1
(Gp:) Mitigada?
50 Clientes????
! Demasiadas pegas ¡
66
Paso de mensajes (Comunicación Directa Asimétrica)
Mejor admitir un recibir de cualquier proceso (no uno concreto)
(Gp:) C1
(Gp:) C2
(Gp:) S
(Gp:) int recibir (char * msj)
(Gp:) Pid del proceso remitente
(Gp:) int recibir (int * remitente, char * msj)
(Gp:) equivalentes
(Gp:) repeat
remitente := recibir (&msjp);
enviar (remitente, respuesta (msjp));
forever
(Gp:) Servidor
¿Más de un servidor?
(Gp:) int enviar (char * msj)
(Gp:) Pid del proceso que recibió???
(Gp:) C
(Gp:) S1
(Gp:) S2
67
Paso de mensajes (Comunicación Indirecta)
(Gp:) bPeti
(Gp:) PC
(Gp:) PS
(Gp:) 1 ? 1
(Gp:) bPeti
(Gp:) PC
(Gp:) PS1
(Gp:) PSm
(Gp:) 1 ? M
(Gp:) bPeti
(Gp:) PC1
(Gp:) PCn
(Gp:) PS1
(Gp:) PSm
(Gp:) N ? M
¿Quién recibe?
Indeterminismo
Justicia
Integridad
(Gp:) bPeti
(Gp:) PC1
(Gp:) PCn
(Gp:) PS
(Gp:) N ? 1
¿De quién
recibí?
(Gp:) PCn
enviar (buzon, msj) recibir (buzon, msj)
(Gp:) int recibir (buzon, msj)
(Gp:) PCn
68
Paso de mensajes (Comunicación Indirecta)
Los enlaces pueden ser Unidireccionales o Bidireccionales
(Gp:) PC
(Gp:) PS
¿ Problemas ?
(Gp:) PC1
(Gp:) PS
(Gp:) PC2
¿ Y aquí ?
Lo normal Unidireccionales:
(Gp:) bPeti
(Gp:) PC
(Gp:) PS1
(Gp:) PS2
(Gp:) bResp
(Gp:) ¿ Código del Cliente y de los Servidores ?
Lo más general:
(Gp:) B1
(Gp:) P2
(Gp:) P4
(Gp:) P5
(Gp:) B2
(Gp:) P3
(Gp:) P1
Varios Procesos
Varios Buzones
Todo dinámico
69
Paso de mensajes (Comunicación Indirecta)
(Gp:) type Buzones is private;
function Crear (nombreB: Nombres ) return Buzones;
function Conectarse (nombreB: Nombres) return Buzones;
procedure Enviar (b: in out Buzones; msj: Mensajes);
procedure Recibir (b: in out Buzones; msj: out Mensajes);
procedure Destruir (b: in out Buzones);
(Gp:) Un modelo:
(Gp:) Capacidad
(Gp:) *
(Gp:) *
(Gp:) ? Propietario
(Gp:) *
Excepción ? buzonInexistente, …
¡ Problemática Destrucción !
(Gp:) Mensajes en el buzón
Procesos bloqueados
Referencias a buzones destruidos
(Gp:) mqd_t mq_open (const char *name, int oflag, .)
int mq_send (mqd_t mqid, const char *msgptr, size_t msgsz, unsigned msgprio)
ssize_t mq_receive (mqd_t msid, char *msgp, size_t msgsz, unsigne *msgprio)
int mq_close (mqd_t mqid)
(Gp:) POSIX
70
Planificación de Procesos ( Criterios )
Planificar ? Elegir el siguiente Pi a ejecutar
(Gp:) JUSTICIA
EFICIENCIA
RENDIMIENTO
MINIMIZAR TIEMPOS
(Gp:) Criterios
(Gp:) Carga
(Gp:) Sin CPU
(Gp:) Ejecutándose
(Gp:) Pi
(Gp:) Tiempo de Retorno
(Gp:) CPU
(Gp:) Tiempo útil
(Gp:) Tiempo inútil
(Gp:) Tiempo de Espera
¿Tiempo de Respuesta?
(Gp:) Pi
(Gp:) < cr>
Criterios difícilmente alcanzables:
Favorecer Pi ? Perjudicar Pj
71
Planificación de Procesos ( PCPU vs PE/S )
(Gp:) PCPU
(Gp:) PE/S
(Gp:) Periodos largos de CPU
(Gp:) Periodos cortos de CPU
?
¿Cómo reconocerlos?
(Gp:) Abandona voluntariamente la UCP
72
Sistemas Batch
No expulsores o expulsores con un quantum grande
Reducen cambios de contexto y mejoran el rendimiento
Por niveles, Primero en llegar primero en servir FCFS, Más corto el siguiente SJF, Tiempo restante menor SRTN
Sistemas interactivos
Expulsores: evita la monopolización de la CPU
Round-Robin, prioridades, múltiples colas, Más corto el siguiente SPN (envejecimiento)
Sistemas de tiempo real
Monotónico en frecuencia
Deadline más próximo el siguiente
Planificación de Procesos ( Políticas )
73
Planificación de Procesos ( Por niveles )
(Gp:) Planificación a
medio plazo
Memoria
(Gp:) Planificación a
corto plazo CPU
(Gp:) CPU
(Gp:) IT2
(Gp:) T2
(Gp:) T3
(Gp:) T5
(Gp:) T1, T2, T3, T4, T5, T6
(Gp:) S.O.
(Gp:) Entrada al sistema
(Gp:) frecuencia alta
(Gp:) frecuencia baja
74
Planificación de Procesos ( Primero en llegar FCFS )
Sólo cuando un proceso abandona voluntariamente la CPU, la misma se asigna al proceso que lleva más tiempo preparado (FIFO)
D
C
(Gp:) A
(Gp:) B
(Gp:) A
(Gp:) D
(Gp:) B
(Gp:) C
(Gp:) D
(Gp:) B
(Gp:) C
(Gp:) A
(Gp:) E/S
Sencillo, pero ? Ausencia de política
(Gp:) D
(Gp:) C
(Gp:) B
(Gp:) A
(Gp:) 4 4 4 8
(Gp:) D
(Gp:) C
(Gp:) B
(Gp:) A
(Gp:) 8 4 4 4
(Gp:) Tesp
(Gp:) Tret
(Gp:) 9
(Gp:) 14
(Gp:) Tesp
(Gp:) Tret
(Gp:) 6
(Gp:) 11
"Efecto convoy"
(Gp:) {PE/S}n
(Gp:) PUCP
(Gp:) PE/S
(Gp:) {PE/S}n-1
(Gp:) PUCP
(Gp:) E/S
(Gp:) T >>
(Gp:) T <
75
Planificación de Procesos ( Efecto convoy )
PUCP = {10UCP + 2E/S}* PE/S = {1UCP + 2 E/S}*
(Gp:) PUCP
(Gp:) PE/S
CPU al 100%, pero tan sólo 30 unidades de tiempo en E/S
CPU al 100% y además, 55 unidades de tiempo en E/S
(Gp:) PUCP
(Gp:) PE/S
(Gp:) ??
76
Planificación de Procesos ( El más corto primero SJF )
(Gp:) Objetivo: Minimizar Tesp/ret
(Gp:) 8
(Gp:) 5
(Gp:) 4
(Gp:) 3
(Gp:) CPU
3
4
5
8
¿Óptimo?
(Gp:) ¿Dónde esperan los procesos?
(Gp:) CPU
(Gp:) preparados
¿Aplicable SJF en planificación a largo y a corto plazo?
(Gp:) ¿Más corto?
Tiempo total de CPU
Lo declara el usuario
Si engaña ? KILL
(Gp:) ¿Más corto?
(Gp:) Sistemas interactivos
(Gp:) Contraejemplo
(Gp:) 0 1 2 3 4
(Gp:) A(2)
B(4)
(Gp:) C(1)
D(1)
E(1)
77
Variante expulsora del SJF.
Cuando llega un trabajo nuevo, comparar su petición de tiempo
con el tiempo que le queda al actual. Seleccionar el menor.
Favorece a los trabajos nuevos
0 1 2 3 4 5 6 7
A(2)
B(4)
C(1)
D(1)
E(1)
¿Tiempo medio de espera?
Planificación de Procesos ( Tiempo restante menor SRTN )
78
Planificación de Procesos (Round Robin)
"Todos iguales": Turno Rotatorio o Rodajas de Tiempo
A cada Pi que pasa a ejecución se le dá una rodaja "cuanto" de tiempo
(Gp:) La consume totalmente y se le expulsa
(Gp:) Pi
(Gp:) rodaja
(Gp:) La usa parcialmente y abandona voluntariamente la UCP
(Gp:) Pi
(Gp:) sleep, wait, exit
Política FIFO de gestión de la cola de preparados
Dos cuestiones de diseño:
¿Cómo elegir el tamaño de la rodaja?
¿Cómo determinar el fin de rodaja?
Ley del 80%
79
Planificación de Procesos (Round Robin)
¿Cómo elegir el tamaño de la rodaja?
Sea Tcc = 5 mseg (mucho)
Rodaja pequeña 20 mseg => Burocracia del 20%
Rodaja grande 500 mseg => Burocracia del 1%
(Gp:) UCP útil
(Gp:) Respuesta lenta a
usuarios interactivos
(Gp:) ¿Degenera en FCFS?
(Gp:) Mejor
interactividad
(Gp:) Ejemplo: P1, P2, P3 => 24, 3 y 3. Rodajas 4 vs 12 y Tcc = 0,5
P1
P2
P3
P1
(Gp:) P1
(Gp:) P1
(Gp:) P1
(Gp:) P1
(Gp:) 33,5
(Gp:) P1
(Gp:) P2
(Gp:) P3
(Gp:) P1
(Gp:) 31,5
Valores comunes:
20..50 mseg
80
Planificación de Procesos (Round Robin)
¿Cómo determinar el fin de rodaja?
Una interrupción periódica
(Gp:) P1
(Gp:) P2
(Gp:) P3
(Gp:) P4
(Gp:) sleep
(Gp:) ¿Somos justos con P3?
(Gp:) ¿viable?
F(int) en 68901 [1µseg..20mseg]
Dar 2 rodajas
Resetear interrupción
Sumar ticks de una interrupción más frecuente
(Gp:) P1
(Gp:) P2
(Gp:) sleep
(Gp:) P3
(Gp:) P4
81
Planificación de Procesos (Prioridades)
"Unos más importantes que otros": Cada Pi prioridad explícita
(Gp:) 0 N
N 0
(Gp:) mín
(Gp:) máx
(Gp:) expulsora
(Gp:) P3
(Gp:) P7
(Gp:) P1
UCP siempre ejecuta Pi más prioritario
UCP libre ? ejecutar Pi más prioritario
Igualdad de prioridad ? FCFS, Round Robin
Prioridades estáticas vs dinámicas
(Gp:) Sencillo pero inanición
(Gp:) P3
(Gp:) P7
(Gp:) P1
(Gp:) P9
(Gp:) ¿ tiempo real ?
(Gp:) no expulsora
(Gp:) P3
(Gp:) P7
(Gp:) P1
82
Planificación de Procesos (Prioridades dinámicas)
Evitar la inanición:
Disminuir la prioridad a medida que se usa la UCP
Aumentar la prioridad si se está tiempo en preparados
¿ Favorece a los trabajos cortos ?
(Gp:) PE/S vs PUCP
Favorece a los Pi ligados a E/S
¿Cuáles son PE/S?
¿Todo el tiempo será PE/S?
(Gp:) PE/S aquellos que usen una parte menor de la rodaja de UCP
Ejemplo con rodajas de 100 mseg:
P1 usa 2 mseg de UCP ? PE/S
P2 usa 25 mseg de UCP ? PUCP
(Gp:) Prio (P1) = 100/2 = 50
Prio (P2) = 100/25 = 4
¿Rango de prioridades [0..N]?
(Gp:) Estáticas muy bajo ? 16
Dinámicas muy variable
83
Planificación de Procesos (Múltiples colas)
"Mezcla de políticas": Cada Pi asociado a una cola de forma estática
(Gp:) Prioridad
(Gp:) 3
(Gp:) 2
(Gp:) 1
(Gp:) 0
(Gp:) FCFS
(Gp:) Round
Robin
(Gp:) Quantum
(Gp:) 4
(Gp:) 8
(Gp:) 16
Dos elecciones:
Seleccionar cola
Seleccionar proceso dentro de la cola
(Gp:) ¿Expulsora?
84
Planificación de Procesos (Múltiples colas realimentadas)
"Mezcla de políticas": Cada Pi asociado a una cola de forma dinámica
Menos Cambios de Contexto
(Gp:) Prioridad
(Gp:) 4
(Gp:) 3
(Gp:) 2
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) + Rodajas Variables
2
4
8
16
Rodajas para Pi ? 1, 2, 4, 8, 16
Favorecer selectivamente PE/S
(Gp:) Prioridad
(Gp:) 3 Terminal
2 E/S
1 Rodaja corta
0 Rodaja larga
Consumir rodajas:
Bajar de prioridad
85
Planificación de Procesos (MINIX 3)
(Gp:) /usr/src/kernel/proc.h
(Gp:) Pi
(Gp:) SI consumió su rodaja
Nueva rodaja
Prioridad++ ¡Menor!
Encolar_Al_Final
SINO
Encolar_Al_Principio
(Gp:) sched
(Gp:) Preparados
(Gp:) MaxPrioridad
(Gp:) MinPrioridad
(Gp:) RoundRobin
(Gp:) proc[log].p_nextready
86
Planificación de Procesos ( Pi más corto siguiente SPN )
(Gp:) CPU
(Gp:) preparados
(Gp:) ¿Más corto?
(Gp:) ¿Más corto?
(Gp:) SJF
(Gp:) SPN
(Gp:) Tiempo de próxima posesión de UCP
?
(Gp:) ¿Predicción? (?i) ?
?i+1 = F (ti, ?i)
?i+1 = ? ti + (1- ?) ?i y ? = 1/2
Predicción
(Gp:) ?i ?
(Gp:) ti ?
10
6
8
4
(Gp:) 6
(Gp:) 6
(Gp:) 6
(Gp:) 4
(Gp:) 5
(Gp:) 13
(Gp:) 9
(Gp:) 13
(Gp:) 11
(Gp:) 13
(Gp:) 12
87
Dado
m eventos periódicos
evento i ocurre en el periodo Pi y precisa Ci segundos
El sistema es planificable si
Hard real time vs Soft real time
Eventos: periódicos vs aperiódicos
(Leer las secciones 7.4.2, 7.4.3 y 7.4.4)
Planificación de Procesos ( Sistemas de Tiempo Real )
88
Separar qué se puede hacer de cómo hacerlo
Un proceso puede saber cuáles de sus threads hijos son los más importantes y asignarles prioridad
Algoritmo de planificación parametrizado
Mecanismo en el kernel
Los procesos de usuario ponen el valor de los parámetros
Los procesos de usuario indican la política
Planificación de Procesos ( Política vs Mecanismo )
pthread_attr_setschedpolicy(.) => FIFO, RR, OTHERS
89
Quantum por proceso de 50 mseg
Cada thread ejecuta 5 mseg de ráfaga de CPU
Planificación de Threads ( Espacio de usuario )
90
Planificación de Threads ( Espacio de kernel )
Quantum por proceso de 50 mseg
Cada thread ejecuta 5 mseg de ráfaga de CPU
91
Sistemas multiprocesador
(Gp:) µP1
(Gp:) µP2
(Gp:) µP3
(Gp:) µP4
Cada µP su cola
(Gp:) Peligro de carga desequilibrada
(Gp:) µP1
(Gp:) µP2
(Gp:) µP3
(Gp:) µP4
¡ Ojo ! ? Spin Lock
Planificar ? ¿Qué thread? ¿En qué núcleo?
Tiempo compartido Threads independientes Cola única
(Gp:) No escalable con aumento núcleos
(Gp:) Espera activa si FR ? Spin Lock
(Gp:) ¡Estoy en RC! ? Alarga rodaja
(Gp:) Problemática caches ? Afinidad
92
Sistemas multiprocesador
Ordenando 128.000 claves "burbuja" en Intel Core 2 Quad Q6600 2,46GHz
(Gp:) µP0
(Gp:) 4MB L2
(Gp:) µP1
(Gp:) µP2
(Gp:) 4MB L2
(Gp:) µP3
sched_setaffinity
93
Sistemas multiprocesador
Espacio compartido Threads cooperantes Apropiarse {µP}n
(Gp:) Núcleo ocioso cuando Pi.bloqueado
(Gp:) Sin multiprogramación ? ¡Menos burocracia!
(Gp:) Sin "n" núcleos libres no me ejecuto
(Gp:) Servidor Web con {threads} variable
94
Sistemas multiprocesador
Planificar por pandillas Threads cooperantes Tiempo/Espacio
(Gp:) Espacio compartido
(Gp:) Tiempo compartido
 Página anterior | Volver al principio del trabajo | Página siguiente  |